Prime Number Theorem

The prime number theorem may refer to any one of many different results estimating the prime counting function π. Here we present the most commonly stated version, and one of the weaker versions.

Theorem
π(x)xlogx

This claim is simply that the relative error between π(x) and xlogx tends to 0. This makes no claim about the absolute error π(x)xlogx, for which better results exist, as well as better approximating functions.


The prime number theorem, as proven here, is merely a consequence of a closely related result for the second Chebyshev function. As such, the main work involved in proving the theorem comes from that that theorem. Here we just show that they are equivalent.

Theorem
ψ(x)xπ(x)xlogx
Proof

From this result we have

ψ(x)=pxlogplogxlogppxlogplogxlogp=pxlogx=π(x)logx.

For a lower bound, we have for any ϵ(0,1)

ψ(x)x1ϵpxlogpx1ϵpxlog(x1ϵ)=(1ϵ)logx(π(x)π(x1ϵ))=(1ϵ)logx(π(x)+O(x1ϵ))=π(x)log(x)+O(x1ϵ)

noting that logx=O(x1ϵ).

Combining these and dividing by x gives the inequality

π(x)logxxψ(x)xπ(x)logxx+O(xϵ).

It is then clear by the pinching theorem that the prime number theorem implies ψ(x)x because limxO(xϵ)=0.

For the reverse implication, we can derive from the above inequality

ψ(x)x+O(xϵ)π(x)logxxψ(x)x

and again the result follows from the pinching theorem.


Corollary
π(x)Li(x)
Proof

First note that we have by direct comparison that

Li(x)=2xdtlogt2xdtt=logxlog2

and thus Li(x) as x.

Hence by L'Hopital's Rule and the fundamental theorem of calculus we have

limxLi(x)x/log(x)=limx1logx1(logx)1(logx)2=limx111logx=1.